Lamping, J. and Rao, R., “The Hyperbolic Browser: A Focus+Context Technique for Visualizing Large Hierarchies”, Journal of Visual Languages and Computing, Vol. 7, 1996, pp. 33-55, disclose techniques for laying out a hierarchy such as a tree on a negatively curved space (e.g., a hyperbolic plane) such that distance between parent and child and between siblings is approximately the same everywhere. A recursive algorithm lays out each node based on local information, allocating a wedge of the hyperbolic plane for the node's descendants. The algorithm places all the children along an arc in the wedge, at an equal distance from the parent node, and at least a minimum distance (or base spacing) apart from each other. The layout of a node depends only on the layout of its parent and on the node structure of two or three generations starting from the parent. Therefore, the layout can be done incrementally, such as by initially laying out the nodes nearest the root and by then adding more nodes as more of the structure is traversed. They also disclose techniques for mapping the plane onto a Euclidean display region such as a unit disk. Initially, a tree has its root at the center or focus of the display region, but the display can be smoothly transformed to bring other nodes into focus. Changes of focus can be implemented by adjusting the focus of the mapping from the hyperbolic plane to the Euclidean plane, such as by a transformation in the hyperbolic plane that moves a new focus to the location that is mapped to the center of the unit disk.
Lamping et al., U.S. Pat. No. 5,590,250, disclose similar layout techniques in which each node has a data structure that includes its position and radius and, if it has children, a link to a list of children; complex numbers are used to represent positions in the negatively curved space such as hyperbolic plane. Lamping et al. also disclose similar mapping techniques in which a transformation is performed on positions in a layout space and the transformed positions are then mapped to obtain positions on a display; mapping is performed recursively, beginning at the root node.
The above documents are incorporated herein by reference in their entireties.
The hyperbolic tree technique disclosed by Lamping et al. provides a smoothly-varying focus+context or fisheye view. The display space allocated to a node falls off continuously with distance from the focus. The context always includes several generations of parents, siblings, and children, making it easy for the user to explore the hierarchy without getting lost. The tree is initially displayed with its root at the center, but the display can be smoothly transformed to bring other nodes into focus.
The hyperbolic tree technique supports effective interaction with much larger hierarchies than conventional hierarchy display techniques and complements the strengths of other novel tree browsers.
A lot of work has been done to visualize the unweighted hyperbolic trees. However, no study has been proposed about the weighted tree layout based on the hyperbolic geometry. Since weighted trees are very common in real applications, such as weighted topic trees, weighted organization charts, weighted file directories, etc. the inventor persists in the improvement on visualizing the weighted trees.